package com.moyoutian.leetcode;

/**
 *
 * 226. 翻转二叉树
 * 翻转一棵二叉树。
 *
 * 示例：
 *
 * 输入：
 *
 *      4
 *    /   \
 *   2     7
 *  / \   / \
 * 1   3 6   9
 * 输出：
 *
 *      4
 *    /   \
 *   7     2
 *  / \   / \
 * 9   6 3   1
 * 备注:
 * 这个问题是受到 Max Howell 的 原问题 启发的 ：
 *
 * 谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
 * 通过次数310,715提交次数394,285
 */
public class Demo226 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
//        invertTree();
    }

    public static TreeNode invertTree(TreeNode root) {
        invertTree1(root);
        return root;
    }

    public static void invertTree1(TreeNode root) {
        if (root == null) {
            return;
        }
        invertTree1(root.left);
        invertTree1(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }


}
